#include <bits/stdc++.h>

using namespace std;

// 尼姆博弈(SG定理简单用法展示)
// 一共有 n 堆石头，两人轮流进行游戏
// 在每个玩家的回合中，玩家需要 选择任一 非空 石头堆，从中移除任意 非零 数量的石头
// 如果不能移除任意的石头，就输掉游戏
// 返回先手是否一定获胜
// 对数器验证

// 时间复杂度O(n)
// 充分研究了性质
string nim1(vector<int>& arr)
{
    int eor = 0;
    for(int x : arr) eor ^= x;
    return eor != 0 ? "先手" : "后手";
}

// sg函数去求解
// 过程时间复杂度高，但是可以轻易发现规律，进而优化成最优解
// 证明不好想，但是从sg表出发，去观察最终的解，要好做很多
string nim2(vector<int>& arr)
{
    int mx = 0;
    for(int x : arr) mx = max(mx, x);
    // 50 17 20 35
    // sg[50] ^ sg[17] ^ sg[20] ^ sg[35] = sg[总]
    // sg[总] != 0，先手赢
    // sg[总] == 0，后手赢
    int sg[mx + 1];
    memset(sg, 0, sizeof sg);
    bool appear[mx + 1];
    for(int i = 1; i <= mx; ++i)
    {
        memset(appear, 0, sizeof appear);
        // 0             sg[0] = 0
        // 1 -> 0        sg[1] = 1
        // 2 -> 1, 0     sg[2] = 2
        // 3 -> 2, 1, 0  sg[3] = 3
        for(int j = 0; j < i; ++j) appear[j] = true;
        for(int s = 0; s <= mx; ++s)
        {
            if(!appear[s])
            {
                sg[i] = s;
                break;
            }
        }
    }
    // 打印sg表之后，可以发现，sg[x] = x
    // 那么eor ^= sg[x] 等同于 eor ^= x
    // 从sg定理发现了最优解
    int eor = 0;
    for(int x : arr) eor ^= sg[x];
    return eor != 0 ? "先手" : "后手";
}

// 为了验证
vector<int> randomArray(int n, int v)
{
    vector<int> ans(n);
    for(int i = 0; i < n; ++i) ans[i] = rand() % v;
    return ans;
}

int main()
{
    srand(time(nullptr));
    int N = 200;
    int V = 1000;
    int testTimes = 10000;
    cout << "测试开始" << endl;
    for(int i = 0; i < testTimes; ++i)
    {
        int n = rand() % N + 1;
        vector<int> arr = randomArray(n, V);
        string ans1 = nim1(arr);
        string ans2 = nim2(arr);
        if(ans1 != ans2) cout << "出错了！" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}